package _11_整理题目._4_动态规划._跳台阶_扔鸡蛋;

import org.junit.Test;

/**
 * 1、递归
 * 2、记忆化搜索递归，从顶向下，搜索、记忆 mem[i]
 *
 * 3、动态规划，从底向上 计算所有的 dp[i]
 * 4、滚动数组
 */
public class _00_斐波那契数列 {
    
    public int fib1(int n) {
        if (n < 2) return n;
        return fib1(n-1)+fib1(n-2);
    }

    public int fib2(int n) {
        if (n < 2) return n;
        int[] mem = new int[n+1];
        return memSearch(mem, n);
    }
    private int memSearch(int[] mem, int n) {
        if (n < 2) return n;
        if (mem[n] == 0) {
            mem[n] = memSearch(mem, n-1) + memSearch(mem, n-2);
        }
        return mem[n];
    }
    
    public int fib3(int n) {
        if (n < 2) return n;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i=2; i<=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public int fib4(int n) {
        if (n < 2) return n;
        int a = 0, b = 1;
        int c = 0;
        for(int i=2; i<=n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    
    @Test
    public void main() {
        System.out.println(fib1(33));
        System.out.println(fib2(33));
        System.out.println(fib3(33));
        System.out.println(fib4(33));
    }
}
